//
//  main.cpp
//  MergeSort
//
//  Created by chenyh on 2021/2/23.
//

#include <iostream>
using namespace std;
/**
 假设有一个待排序的数组 D[0,1,2,...,n–1]，D 有 n 个元素，归并排序算法的做法就是
 先将 D 划分成两个子序列，然后递归地在每个子序列上进行划分和排序，直到每个子序列 的元素个数为 1，然后合并所有的子序列。在划分数组的时候，我们一般偏向于采用平衡 划分法，即尽可能地让划分后的两个子序列的长度相当。因为划分不平衡，很容易导致归 并排序退化成冒泡排序或者选择排序，其时间复杂度为 O(n2)。
 归并排序的关键操作是合并两个已排序的子数据集。基本的合并算法可以表述为:我 们取两个输入数组 A 和 B，划分一个额外的数组 C，其长度为 A 和 B 的长度之和，设置 3 个指针 AStr、BStr 和 CStr。CStr 永远指向 C 数组中需要插入的元素的位置。初始状态下， AStr 和 BStr 分别指向 A 和 B 的首元素，然后比较这两个元素的大小，将较小的元素插入 到 C 数组中 CStr 所指向的位置，CStr 后移一个位置;接着被复制了元素的数组指针后移 一个单位，指向较小元素的后继元素。重复进行比较，直到某一个输入数组所有元素都被 处理，则将另一个数组的剩余元素依次复制到 C 数组的末尾，如此就完成了依次归并
 
 
 合并算法的时间复杂度是线性的，最多进行 n–1 次比较。当 n=1 时， 每个子序列只有一个元素需要排序，我们停止归并排序操作;否则，我们需要对每个子序 列进行递归的归并排序，然后按照上面的合并算法将所分成的两个子序列合并起来，构成 了有序的序列
 
 算法描述可以看出，归并排序是一个典型的运用分治思想的算法例子， 我们可以很容易地用递归合并方式实现它。在整个归并排序过程中，子序列的合并是一个非常 重要的操作，我们先来实现两个数组的合并操作函数，算法实现如下:
 
 
 归并算法的运行时间与程序迭代的次数和每一趟排序的合并 时间有关，其值等于归并的趟数乘以每趟的合并时间。合并函数运行的时间是线性的。当 某个子序列的元素个数为 n=1 时，这一步的排序时间为一个常数，我们记为 O(1) = 1;当 n>1 时，完成 n 个数归并的时间我们可以看成是，两个大小为 n/2 的序列的递归排序的时 间与这两个序列合并的时间的和，并且合并函数的时间是线性的。所以
 T(n) = 2T(n/2) + n
 T(1) = 1
 T(n) = 2T(n/2)+n = 4T(n/4)+2n=...=2kT(n/2k)+kn
 其中 k 为算法迭代的次数，即 n 个元素二分化的次数，则 k = log2n。将 k 带入上式，
 所以归并排序的时间复杂度为 T(n) = nlog2n+n = O(nlog2n)。
 
 */


/** */
template <class T>
void merge(T A[], T B[],T C[],int lengthA,int lengthB) {
    cout<<&A<<endl;
    cout<<&B<<endl;
    cout<<&C<<endl;
    cout<<lengthA<<endl;
    cout<<lengthB<<endl;
    //lengthA 和 lengthB 分别表示 A 和 B 的长度
    int i=0,j=0,counter=0;
    while (counter < lengthA+lengthB) {
        if (A[i] < B[j]) {
            C[counter] = A[i];  //将较小的元素先放到c中
            i++;
            counter++;
        }else {
            C[counter] = B[j];
            j++;
            counter++;
        }
        if (i == lengthA) { //判断a是否遍历完成，游标是否到a的末尾
            while (j < lengthB) { //如果a遍历完成且b未完成
                C[counter] = B[j]; //将b中剩余的元素依次存入c中剩下的位置
                j++;
                counter++;
            }
        }else if(j == lengthB)
        {//如果b完成而a未完成，则将a中剩下的元素依次存入c中剩下的位置
            while (i < lengthA) {
                C[counter] = A[i];
                i++;
                counter++;
            }
        }
    }
}

/**归并算法*/
template <class T>
void mergeSort(T A[],int n) {
    if (n > 1) {
        int i = n/2;
        int j = n-i;
        T B[i];
        T C[j];
        for (int k = 0; k < i; k++){ //将n>1时，将数组划分成子序列
            B[k]=A[k];
        }
        for (int k=0; k < j; k++) {
            C[k] = A[k+i];
        }
        cout<<i<<endl;
        cout<<j<<endl;
        cout<<'Q'<<endl;
        
        mergeSort(B, j);            //对每个子序列递归 进行归并排序
        mergeSort(C, j);            //
        merge(B,C,A, i, j);         //合并有序的子序列
    }
}

void testDiGui(int i) {
    i--;
    if (i > 0) {
        cout<<i<<"次"<<endl;
        testDiGui(i);
    }
    
    cout<<i<<endl;
    
}


int main(int argc, const char * argv[]) {
    // insert code here...
   
    int a[] = {5,4,11,20,19,30};
    
    mergeSort(a, 6);
    cout<<"输出排序结果："<<endl;
    for (int i=0; i<6; i++) {
        
        cout<<a[i]<<endl;
    }
    
    
    return 0;
}
